class Trie;
using TrieNode = Trie;

class Trie
{
public:
    // 插入一个字符串
    void insert(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (!node->children.count(c))
            {
                node->children[c] = new Trie;
            }
            node = node->children[c];
            ++node->viaCount;
        }
        ++node->endCount;
    }

    bool search(string word)
    {
        return count(word);
    }

    bool startsWith(string prefix)
    {
        return prefixCount(prefix);
    }

    // 字符串s的数量
    int count(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (node->children.count(c))
            {
                node = node->children[c];
            }
            else
            {
                return 0;
            }
        }
        return node->endCount;
    }

    // 以s为前缀的字符串数量
    int prefixCount(const std::string &s)
    {
        TrieNode *node = this;
        for (char c : s)
        {
            if (node->children.count(c))
            {
                node = node->children[c];
            }
            else
            {
                return 0;
            }
        }
        return node->viaCount;
    }

    int nodeEndCount() const
    {
        return endCount;
    }

    int nodeViaCount() const
    {
        return viaCount;
    }

    bool existChild(char c) const
    {
        return children.count(c);
    }

    const TrieNode *child(char c) const
    {
        if (children.count(c))
        {
            return children.at(c);
        }
        return nullptr;
    }

    ~Trie()
    {
#ifdef TRIE_DECONSTRUCT
        for (auto &[_, child] : children)
        {
            if (child != nullptr)
            {
                delete child;
            }
            child = nullptr;
        }
#endif
    }

private:
    std::unordered_map<char, TrieNode *> children;
    int endCount = 0;
    int viaCount = 0;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */